
/* A simple cache simulator that takes in input from 
   Valgrind traces and cache specifications and determines
   the number of hits, misses, and evictions that occur
   for those sequences of instructions with that cache. 

   Ben Marks, January 2014
*/

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <getopt.h>
#include <stdint.h>
#include <assert.h>

#define MAXFILE 256

static uint32_t hitCount = 0;
static uint32_t missCount = 0;
static uint32_t evictionCount = 0;
static uint32_t verbose = 0;
static char fileName[MAXFILE];


/* Enable some extra debugging output */
//#define DEBUG

typedef struct {
  uint64_t * storedTags;    // Tags in the cache
  uint32_t * instructionNo; // Last instruction used for each tag
  uint32_t numSoFar;        // How many lines are used?
  uint8_t numLines;         // How many lines do we have 
} cacheSet;

/* Prints a usage string and exits */
static void usage() {

  printf("\nUsage: ./csim  < Flags > ");
  printf("\n\t -h      : Display this message");
  printf("\n\t -v      : Verbose output for traces");
  printf("\n\t -s < s >: Required number of set index bits");
  printf("\n\t -E < E >: Required number of lines per set");
  printf("\n\t -b < b >: Required number of block bits");
  printf("\n\t -t < F >: Required Valgrind trace file, F");

  exit(1);

}

/* Wrapper around malloc to check return value. 

   Returns an allocated block, or exits if malloc 
   fails.
*/
static void * Malloc( size_t size ) {

  void * toRet = malloc( size );
  if ( toRet ) {
    return toRet;
  }
  perror("malloc");
  exit(1);
}

/* Given teh number of bits in the block and set index, 
   create a mask that isolates the set and tag bits.

   Nothing is returned, but the set and tag bit masks are 
   passed in by reference and modified.
*/
static void makeMasks(uint64_t setIndexBits, uint64_t blockIndexBits,
	       uint64_t * setMask, uint64_t * tagMask ) {

  int i, startBit, endBit;
  uint64_t localMask = 0;
  uint64_t shifter = 1;
  
  /* Mask for the set index */
  startBit = blockIndexBits;
  endBit = startBit + setIndexBits;
  for ( i = startBit; i < endBit; i++ ) {
    localMask |= (shifter << i);
  }
  *setMask = localMask;

  /* Mask for the tag bits */
  localMask = 0;
  startBit = blockIndexBits + setIndexBits;
  endBit = 64;
  for ( i = startBit; i < endBit; i++ ) {
    localMask |= (shifter << i);
  }

  *tagMask = localMask;
  
}

/* Given a number and a mask, extract the bits in 
   the mask and return them. 
*/
static uint64_t extractMask( uint64_t addr, uint64_t mask ) {

  if ( ! mask ) {
    return 0;
  }

  uint64_t localMask = mask;
  uint64_t toRet = addr & mask;
  while ( ! ( localMask & 1 ) ) {
    toRet     >>= 1;
    localMask >>= 1;
  }

  return toRet;

}

/* Read in and set state variables based on arguments passed 
   in from the command line. 

   Returns: Nothing, but flags for verbosity, the number of set
   and block bits, the number of lines, and the file name are modified. 
*/
static void parseArgs( int argc, char ** argv,
		uint32_t * setBits, uint32_t * numLines,
		uint32_t * blockBits ) {

  int retVal;
  while ( (retVal = getopt( argc, argv, "hvs:E:b:t:" ) ) >= 0 ) {
    switch( retVal ) {
    case 'h':
      usage();
      break;
    case 'v':
      verbose = 1;
      break;
    case 's':
      *setBits = atoi( optarg );
      break;
    case 'E':
      *numLines = atoi( optarg );
      break;
    case 'b':
      *blockBits = atoi( optarg );
      break;
    case 't':
      strncpy( fileName, optarg, MAXFILE );
      break;
    default: /* ? */
      usage();
      break;

    }
  }


}


/* Get the next data instruction from the Valgrind trace file. 

   Returns 0 if there are no instructions left or 1 if a
   new instruction has been read. If 1 is returned, then
   type and addr are modified to contain the type of access
   and the relevant address as appropriate.

   If verbose is specified, then the instruction is printed.
*/
static int getNextAccess( FILE * f, char * type, uint64_t * addr ) {

  char buf[128];
  char * retVal;
  buf[0] = '\0';
  // Skip instruction loads
  while ( (retVal = fgets( buf, 128, f )) && buf[0] != ' ' ) { }
  if ( ! retVal ) { // EOF
    return 0;
  }

  if ( verbose ) {
    *strchr(buf, '\n') = '\0'; // Don't print newline
    printf("\n%s ", &buf[1]);
  }

  // buf has an instruction that involves data
  *type = buf[1];
  if ( *type != 'M' && *type != 'L' && *type != 'S' ) { 
    // Invalid instruction or trace file
    printf("\nError: Invalid trace file instruction %c", *type);
    exit(1);
  }

  char * iter = strchr( &buf[3], ',' );
  if ( ! iter ) {
    printf("\nError: Invalid trace file instruction formatting %s.", buf);
    exit(1);
  }
  *iter = '\0';
  if ( ! sscanf( &buf[3], "%llx", (long long unsigned int * ) addr ) ) {
    // Keep gcc happy and warning free with uint64_t vs long long unsigned int
    printf("\nError: Unable to parse address of instruction %s", buf ); 
    exit(1);
  } 

  // Values are valid
  return 1;

}

/* Check if a tag is in a cache set, updating the
   number of hits / misses / evictions as appropriate.

   If a tag is not in the cache, then the LRU tag
   is evicted for the new tag. 

   If verbose is specified, then hits, misses, nad evictions are 
   printed as they happen.
*/
static void accessAddr( cacheSet * set, uint64_t tag ) {
  int i;
  int numIters = 
    ( set->numSoFar > set->numLines ? set->numLines : set->numSoFar );
  for ( i = 0; i < numIters; i++ ) {
    if ( set->storedTags[i] == tag ) {
      if ( verbose ) {
	printf(" hit ");
      }
      hitCount ++;
      set->instructionNo[i] = set->numSoFar;
      return;
    }
  }

  if ( verbose ) {
    printf(" miss ");
  }
  missCount ++ ;
  uint32_t tagPosition;
  if ( set->numSoFar >= set->numLines ) {
    if ( verbose ) {
      printf( " eviction " );
    }
    evictionCount ++;
    // Must evict the least recently used item
    uint8_t minIdx = 0;
    for ( i = 0; i < set->numLines; i++ ) {
      if ( set->instructionNo[i] < set->instructionNo[minIdx] ) {
	minIdx = i;
      }
    }
    tagPosition = minIdx;
  }
  else {
    tagPosition = set->numSoFar;
  }
  // Add tag to stored tags
  set->storedTags[ tagPosition ] = tag;
  set->instructionNo[ tagPosition ] = set->numSoFar;
  set->numSoFar ++;

  return;


}

int main( int argc, char ** argv ) {

  // Parse arguments and check validity
  uint64_t i = 0;
  uint32_t numSetBit, numLines, numBlockBit; 
  numSetBit = numLines = numBlockBit = verbose = 0;
  parseArgs( argc, argv, &numSetBit, 
	     &numLines, &numBlockBit );
  
  FILE * traceFile = fopen( fileName, "r" );
  if ( ! traceFile ) {
    printf("\nError: Invalid file %s", fileName);
    exit(1);
  }

  // Create masks to isolate sets / tags
  uint64_t setMask, tagMask;
  setMask = tagMask = 0;
  makeMasks( numSetBit, numBlockBit, &setMask, &tagMask );

#ifdef DEBUG
  printf("\nSetNum: %d;  LineNum: %d; BlockNum: %d; verbose: %d",
	 numSetBit, numLines, numBlockBit, verbose);
  printf("\nFile: %s; SetMask: %llu; TagMask: %llu\n\n", 
	 fileName, 
	 (long long unsigned int) setMask, 
	 (long long unsigned int) tagMask);
  /* Keep gcc happy and format warning free */
#endif
  
  // Initialize sets
  uint64_t numSets = 1 << numSetBit;
  cacheSet * sets = Malloc( numSets * sizeof(cacheSet) );
  // Initialize each set
  for ( i = 0; i < numSets; i ++ ) {
    sets[i].numLines = numLines;
    sets[i].numSoFar = 0;
    sets[i].storedTags = Malloc( numLines * sizeof(uint64_t) );
    sets[i].instructionNo = Malloc( numLines * sizeof( uint32_t ) );
  }

  char type;
  uint64_t addr;

  // Execute instructions, keeping track of hits, misses,
  // and evictions. 
  while ( getNextAccess( traceFile, &type, &addr ) ) {
    // Get the set number
    uint64_t setNo = extractMask( addr, setMask );
    uint64_t tag = extractMask( addr, tagMask );
#ifdef DEBUG
    printf("\nAddr: %llu; Set: %llu; Tag: %llu", 
	   (long long unsigned int ) addr, 
	   (long long unsigned int ) setNo, 
	   (long long unsigned int ) tag);
    /* Keep gcc happy and format warning free */
#endif


    switch( type ) {
    case 'M':
      accessAddr( &sets[setNo], tag );
      /* Fall Through - modify has 2 accesses */
    case 'S': // Set - only 1 access
    case 'L': // Load - only 1 access
      accessAddr( &sets[setNo], tag );
      break;
    }
  }

  // Print summary information
  printf("\nhits:%u misses:%u Evictions:%u\n", hitCount, 
	 missCount, evictionCount);

  // Clean Up
  for ( i = 0; i < numSets; i ++ ) {
    free( sets[i].storedTags );
    free( sets[i].instructionNo );
  }
  free ( sets );

  fclose( traceFile );

  return;
}
